class Solution:
    def numSquares(self, n: int) -> int:
        sq = []
        i = 1
        while True:
            if i ** 2 <= n:
                sq.append(i ** 2)
            else:
                break
            i = i + 1
        dp = [i for i in range(n + 1)]
        for i in range(2, n + 1):
            for j in sq:
                if i - j < 0:
                    break
                dp[i] = min(dp[i], dp[i - j] + 1)
        # for i in range(0, n+1):
        #     print("{}\t{}".format(i, dp[i]))
        return dp[-1]


if __name__ == '__main__':
    so = Solution()
    m = 12
    r = so.numSquares(m)
    print(r)
